1. Field of the Invention
This invention is related to the field of peripheral interfaces and, more particularly, to ordering rules and fairness for transactions on such interfaces.
2. Description of the Related Art
Peripheral interface specifications typically specify transaction ordering rules for transactions communicated over the interface. For example, the Peripheral Component Interconnect (PCI) Express™ specification specifies ordering rules among posted transactions, nonposted transactions, and completions. The transaction ordering rules may be designed to prevent deadlock in the system, as well as to ensure the producer-consumer model is supported.
Among other things, the PCI Express (PCIe) ordering rules require that the posted transactions be able to pass nonposted transactions and completions. That is, if a nonposted transaction or completion is blocked from transmission and the posted transaction is not blocked, the posted transaction must be permitted to be transmitted, even if the posted transaction is queued behind the blocked transaction, is younger than the blocked transaction, etc. Similarly, completions must be able to pass nonposted transactions. Other ordering rules may permit passing of transactions, or permit passing of transactions in certain cases. Still other ordering rules do not permit passing in some cases.
Transactions may be blocked due to a lack of resources for handling the transaction. For example, a credit-based system is often used to track available resources in a receiver of a transaction. Credits may be maintained for each available resource for handling a given transaction type, and a credit may be consumed when a transaction of that type is transmitted by a transmitter (and thus consumes the resource in the receiver). The credit is returned to the transmitter when the transaction completes or otherwise frees the resource. If no credit is available for a given transaction type, transactions of that type are blocked until the credit becomes available. A given device on the peripheral interface may be both a transmitter and a receiver of transactions.
Implementing the ordering rules correctly while supporting high performance and fairness among transaction types is complex and error prone. A simple implementation makes posted transactions high priority, completions medium priority, and nonposted transactions low priority. In such an implementation, posted transactions would always pass completions and nonposted transactions, and completions would always pass nonposted transactions. However, such an implementation would not support fairness very well, since the nonposted transactions are only transmitted when there are no posted transactions or completions, regardless of how long the nonposted transactions have been queued awaiting transmission.
Other implementations use a single age counter to track the age of transactions. As each transaction request is received, it is assigned the current value of the age counter and the counter is incremented. By comparing age counter values assigned to each transaction, the age of transactions may be determined. If two transactions are both able to be transmitted, the older transaction can be selected. However, since some transactions can pass others, the age counter can never be made large enough to ensure that it will not overflow. For example, a long string of posted transactions passing a nonposted transaction that is blocked may cause the age counter to overflow, and age information may be lost. Typically, complex logic must be implemented to properly handle the overflow case and not lose age information among the queued transactions.